package com.shigen.demo.algorithm;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效
 * @author shigenfu
 * @date 2022/7/21 12:35 下午
 */
public class IsValid {

  public static void main(String[] args) {
    String str = "()";
    boolean isValid = isValid(str);
    System.out.println(isValid);
  }

  private static boolean isValid(String str) {
    Deque<Character> characters = new LinkedList<>();
    for (int i = 0; i < str.length(); i++) {
      if (str.charAt(i) == '{') {
        characters.push('}');
      } else if (str.charAt(i) == '[') {
        characters.push(']');
      } else if (str.charAt(i)== '(') {
        characters.push(')');
      } else if (characters.isEmpty() || characters.peek() != str.charAt(i)) {
        // 栈已经为空或者栈顶的元素不是当前下标的元素
        return false;
      } else {
        characters.pop();
      }
    }


    return characters.isEmpty();
  }
}
